//给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点总数在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
//
// 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/ 
// Related Topics 树 深度优先搜索 回溯 二叉树 👍 347 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class SolutionOffer34 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root == null) return result;
        dfs1(root, target);
        return result;
    }


    public void dfs1(TreeNode root, int target){
        target -= root.val;
        path.add(root.val);
        if(root.left == null && root.right == null){
            if(target == 0){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        if(root.left != null){
            dfs1(root.left, target); //target是局部变量，回溯的时候自动回到上一个值
            path.remove(path.size()-1);
        }
        if(root.right != null){
            dfs1(root.right, target);
            path.remove(path.size()-1);
        }

    }

    /**
     * 这样写结果会产生重复
     * 以5->4->11->2为例，搜索到2的时候，继续搜索2的左子树，为null且target==0，加入result
     * 继续搜索2的右子树，为null且target==0，加入result,重复加入了两次
     * @param root
     * @param target
     */
    public void dfs(TreeNode root, int target){
        if(root == null){
            if(target == 0){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        target -= root.val;
        path.add(root.val);
        dfs(root.left, target); //target是局部变量，回溯的时候自动回到上一个值
        dfs(root.right, target);
        path.remove(path.size()-1);
    }

//    public static void main(String[] args) {
//        TreeNode root = BinaryTreeFactory.generateBinaryTreeFromArray(new Integer[]{1, 2, 3});
//        int target = 4;
//        new Solution().pathSum(root,target);
//    }
}
//leetcode submit region end(Prohibit modification and deletion)
